package william.greedy;

/**
 * @author ZhangShenao
 * @date 2024/4/28
 * @description <a href="https://leetcode.cn/problems/jump-game/solutions/203549/tiao-yue-you-xi-by-leetcode-solution/">...</a>
 */
public class Leetcode55_跳跃游戏 {
    /**
     * 采用贪心算法
     * 记录当前可以跳到的最远位置maxRight,初始情况maxRight=0
     * 遍历数组,针对当前位置i:
     * - 如果maxRight>=N-1,说明可以到达最后一个下标,直接返回true
     * - 如果i在maxRight范围内,说明之前一定可以通过某种跳跃方式到达当前位置,则更新最远位置maxRight=Max(maxRight,i+nums[i])
     * - 如果i超过maxRight范围内,说明当前位置不可达,则直接返回false
     * 遍历完成,没有到达最后一个位置,返回false
     * <p>
     * 时间复杂度O(N) 只遍历数组一次
     * 空间复杂度O(1)
     */
    public boolean canJump(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return true;
        }

        //记录当前可以跳到的最远位置maxRight,初始情况maxRight=0
        int maxRight = 0;
        int N = nums.length;

        //遍历数组
        for (int i = 0; i < N; i++) {
            if (maxRight >= N - 1) { //如果maxRight>=N-1,说明可以到达最后一个下标,直接返回true
                return true;
            }

            if (i > maxRight) { //如果i超过maxRight范围内,说明当前位置不可达,则直接返回false
                return false;
            }

            //i在maxRight范围内,说明之前一定可以通过某种跳跃方式到达当前位置,则更新最远位置maxRight=Max(maxRight,i+nums[i])
            maxRight = Math.max(maxRight, i + nums[i]);
        }

        //遍历完成,没有到达最后一个位置,返回false
        return false;
    }
}
